#include <stdio.h>
#include <string.h>

int get_off(const char str[], int len, int o_off) {
  int i,j;
  for(i=o_off+1; i<len; i++) {
    for(j=i; j<len; j++) 
      if(str[j] != str[j-i]) {
        break;
      }
    if(j == len) break;
  }
   return i;
}

//int movarray[strlen(str)]
void get_mov(const char str[], int movarray[]) {
  int len = strlen(str);
  int i,j,off;
  for(i=0; i<len; i++) {
    if(i == 0) {
      movarray[0] = 1;
      continue;
    } else if(i == 1) {
      if(str[1] == str[0]) movarray[1] = 2;
      else movarray[1] = 1;
      continue;
    }
    off = 0;
    while(off<i) {
      off = get_off(str,i,off);
      if(str[i] != str[i-off]) {
         movarray[i] = off;
         break;
      }
    }
    if(off == i && str[i] == str[0]) movarray[i]=i+1;
    
  }

}


const char *str_search(const char *haystack, const char *needle, int movarray[]) {
  int i,j;
  for(i=0; haystack[i]; i = i-j+movarray[j]) {
    for(j=0;needle[j];j++,i++)
      if(haystack[i] != needle[j]) break;
    if(!needle[j]) return (char*)haystack+i-j;
  }
  return NULL;
}


int main(){
  const char *needle = "cdxaaaazz";
  int movarray[30];
  get_mov(needle, movarray);
  const char *s = str_search("abcddfcdxaaaabdsfsdfdfdsfdasdfdsfdsfdsfdsfdsfdsfdsfdfdfdsfsdfdsfacdecdxzcdxaaaazz", needle, movarray);
  printf("%s\n",s);
  s = str_search("cdxaaaazcdxaaazzcdxaaaazzxxxf",needle,movarray);
  printf("%s\n",s);
}
